Resolución de problemas mediante búsqueda (Presentación PowerPoint) (página 2)

Partes: 1, 2

La resolución de un problema de IA mediante búsqueda consiste en la aplicación de una determinada estrategia de control que conduzca a encontrar un camino desde el estado inicial hasta algún estado objetivo del espacio de estados.
examinar las posibles secuencias de acciones
seleccionar aquella que sea mejor según un determinado criterio
Los objetivos fundamentales de la resolución de un problema mediante búsqueda son:
Encontrar una solución
Que la solución tenga coste total mínimo:
Coste de búsqueda (coste offline):
Tiempo y memoria necesarios.
Coste del camino solución (coste online).

Resolución mediante búsqueda

Ejercicio Problema del 8-puzzle
Estados?
Operadores?
Coste del camino?
Objetivo?
Puzzle con 8 piezas, hay que llegar del estado inicial al objetivo, moviendo el hueco.
Estado inicial?

Ejercicio Problema de las N reinas
Estados?
Operadores?
Coste del camino?
Tablero con N reinas o damas.
Encontrar configuración de las damas no enfrentadas entre si
Objetivo?
Es esto una solución?
No, se amenazan
Estado inicial?

Ejemplos, I
Problema del 8-puzzle
Estados: posiciones de las piezas y hueco
(setf *estado0*
‘((0 5)(1 4)(2 nil)
(3 6)(4 1)(5 8)
(6 7) (7 3) (8 2))
Operadores:
HuecoA: Dcha – Izda – Arriba – Abajo
Objetivo: (ver gráfico anterior)
Coste operadores: 1
Problema de las 8 reinas (en general de las N reinas/damas):
Coste operadores: 1 (el camino solución siempre tiene coste 8).
Posible representación (1):
estado: N reinas en el tablero
operadores: añadir una reina a una posición vacía.
Posible representación (2):
estado: N reinas en el tablero (no atacándose).
Operadores: añadir una reina en la columna vacía más a la izquierda tal que no sea atacada por ninguna de las ya existentes.
Menos operadores que en la representación (1)

Ejemplos, II
Problemas de Criptoaritmética

Estados: algunas letras sustituidas por dígitos.
Operadores: sustituir una letra por un dígito que no aparece ya dentro del estado.
La solución se encuentra a profundidad conocida.
Todas las soluciones son igualmente válidas luego el coste del camino es 0

FORTY
+ TEN
TEN
——
SIXTY

29786
+ 850
850
——
31486

Ejemplos, III
Misioneros y caníbales
Hay 3 misioneros y 3 caníbales en la orilla izquierda de un río. Un bote puede transportar a 1 ó 2 personas de una orilla a otra.
Objetivo: pasar a todos a la otra orilla.
Condición: No puede ocurrir nunca que si en una orilla hay algún misionero haya a la vez un número mayor de caníbales (se los comerían).
Estados:
Parámetros: número misioneros lado izquierdo, número caníbales lado izquierdo, posición bote (izquierda o derecha).
Se debe verificar la Condición.
Operadores:
Transportar 1 misionero.
Transportar 1 caníbal.
Transportar 2 misioneros.
Transportar 2 caníbales.
Transportar 1 misionero y 1 caníbal.
Coste operador: 1

Ejemplos, IV
Otros ejemplos (más reales):
Problema de mapa de carreteras.
Viajar de una ciudad a otra recorriendo la menor distancia posible.
Problema del viajante de comercio
Un viajante debe viajar recorriendo un conjunto de ciudades. Debe partir de una ciudad inicial y, tras recorrer todas las ciudades, volver a la ciudad de inicio.
Problema clásico: debe visitar exactamente 1 vez todas las ciudades (excepto la de inicio que la visita 2 veces).
Problemas de
Diseño de circuitos.
Navegación de robots.
Montaje mecánico de robots.
Planificación de toma de imágenes (telescopio Hubble).

Búsqueda en árboles, I
Representación de un nodo:
Estado: elemento del espacio de estados que corresponde con el nodo.
Nodo padre: el nodo en el árbol de búsqueda que ha generado este nodo.
Acción/Operador: operador que se aplicó al padre para generar este nodo.
Coste del camino: el coste desde el nodo inicial. Denotado por g(n).
Profundidad en el árbol de búsqueda: número de pasos a lo largo del camino desde el nodo inicial.
Distinguir los conceptos:
Espacio de estados:
Finito
Árbol de nodos: se genera
Finito o infinito
Ejemplo: mapa de carreteras

Búsqueda en árboles, II
Algoritmo de búsqueda en árboles (descripción informal):

funcion búsqueda-árboles (problema, estrategia)
devuelve una solución o fallo
inicializa árbol de búsqueda con estado inicial
bucle hacer
si no hay candidatos para expandir,
entonces devolver fallo
en otro caso
escoger, según estrategia, nodo para expandir
si el nodo es objetivo (contiene estado objetivo)
entonces devolver solución
en otro caso
expandir nodo
añadir nodos resultantes al árbol

Búsqueda no informada vs búsqueda informada
Búsqueda no informada o ciega:
Sólo usan la información de la definición del problema.

Estrategias:
Búsqueda primero en anchura.
Búsqueda primero en profundidad.
Búsqueda limitada en profundidad.
Búsqueda iterativa en profundidad.
Búsqueda bidireccional.
Búsqueda informada o heurística:
Usan la información de definición del problema y el coste del estado actual al objetivo.
Estrategias:
Best first
Búsqueda Avara
A*
IDA*
Mejora iterativa

Estrategias de búsqueda ciega, I
Criterios de evaluación de estrategias:
Completitud (encontrar solución)
Optimización (encontrar la mejor solución)
Complejidad espacial (memoria necesaria)
Complejidad temporal (tiempo necesario)
Estrategias de búsqueda:
Hipótesis:
Todos los operadores tienen el mismo coste (por ejemplo 1).
El factor de ramificación es siempre finito.
Las complejidades temporal y espacial se miden en términos de:
m = profundidad máxima del árbol de búsqueda (puede ser infinito)
d = profundidad de la mejor solución (de la de menor coste)
b = factor de ramificación (máximo nº de sucesores de cualquier nodo del árbol de búsqueda)

Estrategias de búsqueda ciega, II
Búsqueda en anchura:
Completo y óptimo
Complejidad espacial =
Complejidad temporal =
número de nodos expandidos =

Número de nodos generados
Para b=10, 1000 nodos/segundo, 100 bytes/nodo:
d=2, 111 nodos, 0.1 seg., 11 Kb
d=6, 1.000.000 nodos, 18 minutos, 111 Mb
d=12, nodos, 35 años, 111 Tb
Ejemplo: viajante de comercio

Estrategias de búsqueda ciega, III
Búsqueda en profundidad:
No es óptimo
Puede encontrar un camino peor
No es completo
Puede no acabar
Complejidad temporal =
Complejidad espacial =
número de nodos necesarios = un camino hasta una hoja y los hermanos de cada nodo del camino =

Ejemplo: viajante de comercio

Estrategias de búsqueda ciega, IV
Búsqueda limitada en profundidad:
Caso particular de Búsqueda en profundidad. Se utiliza un límite de profundidad (l)
No es óptimo
Puede encontrar un camino peor
No es completo, en general, aunque:
sí es completo cuando

Complejidad temporal =

Complejidad espacial =
número de nodos necesarios = un camino hasta una hoja y los hermanos de cada nodo del camino =

Estrategias de búsqueda ciega,V
Búsqueda iterativa en profundidad:
Son búsquedas en profundidad con límites: 0, 1, 2, 3, 4, …
Es óptimo y completo
Complejidad espacial =
Complejidad temporal
número total de expansiones (los nodos con la profundidad de la mejor solución se expanden 1 vez; los siguientes 2 veces, los siguientes 3 veces, …) =

Método preferido cuando no se conoce la profundidad de la solución.

Búsqueda iterativa en profundidad (abstracción gráfica)
Estrategias de búsqueda ciega, VI

Estrategias de búsqueda ciega, VII
Búsqueda bidireccional:
Buscar simultáneamente desde estado inicial hasta objetivo y viceversa hasta que ambas búsquedas “se encuentren”.
Optimo y completo.
Complejidad espacial y temporal:

Dificultades
Cálculo de predecesores.
Varios estados objetivo.
Significado de “encontrarse las búsquedas”.
Determinación del tipo de búsqueda en cada dirección.
Ejemplo: viajante de comercio

Estrategias de búsqueda ciega, VIII
Búsqueda de coste uniforme:
Los resultados anteriores pueden no verificarse cuando los costes de los arcos son variables ? tener en cuenta costes
Costes variables para los arcos pero:

Para un nodo n se define:
g(n) = coste desde nodo inicial
Se expande el nodo con menor valor de g
Completo y óptimo
Si todos los arcos tienen el mismo coste, se tiene búsqueda en anchura.
Si todos los arcos tienen el mismo coste, g(n)=profundidad(n)
Complejidad espacial y temporal =

Ejemplo: viajante de comercio

Estrategias de búsqueda ciega, IX
Cuadro resumen:

Eliminación de estados repetidos, I
La repetición de estados incrementa la complejidad de la estrategia de búsqueda
Si la estrategia no los detecta (comparar el nodo a expandir con los ya expandidos), un problema resoluble puede llegar a ser irresoluble.
Situación habitual en problemas de rutas y acciones reversibles
Ejemplo: espacio con d+1 estados
Para los d+1 estados (d es la profundidad máxima)
El árbol de búsqueda contendrá 2d ramas. Poda.

Eliminación de estados repetidos, II
Para evitar que se repitan estados, se pueden considerar tres métodos:
No generar un nodo hijo de un nodo si los dos pertenecen al mismo estado
Evitar ramas con ciclos (en un camino desde el nodo inicial, hay dos nodos que pertenecen el mismo estado)
El método 2) incluye al 1)
Si al generar un nodo, su estado asociado, ya ha sido generado por otro nodo, eliminar el nodo peor (y sus descendientes) del árbol de búsqueda
El método 3) incluye al 2) y, por tanto, al 1)
Este método es el más caro (hay que mantener todos los nodos en memoria).
Estructuras de datos
Listas cerradas (nodos expandidos)
Listas abiertas (frontera de nodos no expandidos)
Algoritmo general de búsqueda en grafos
(Russell, 2nd. Ed., sec. 3.5)

Ejemplo
Realizar búsqueda en anchura (eliminando estados repetidos) (suponemos costes=1):

Estado inicial: A
estados objetivo: {G}

(Gp:) A
(Gp:) B
(Gp:) D
(Gp:) C
(Gp:) F
(Gp:) G
(Gp:) E

(Gp:) A
(Gp:) B
(Gp:) D
(Gp:) C
(Gp:) F
(Gp:) G
(Gp:) E
(Gp:) 4
(Gp:) 3
(Gp:) 6
(Gp:) 5
(Gp:) 7
(Gp:) 2
(Gp:) 1
(Gp:) SOLUCIÓN

Problemas de satisfacción de restricciones, I
Constraint Satisfaction Problems (CSP)
Problema definido por:
Un conjunto de variables cuyos valores están definidos en un dominio (finitos o infinito)
Un conjunto de restricciones que involucran una o más variables del problema (ecuaciones lineales/no lineales)
Los estados del problema que se definen mediante asignaciones variable – valor
Una función objetivo que optimice la solución del CSP
Estrategia de backtracking
Búsqueda en profundidad
Asigna valores a variables (una cada vez)
Retrocede en el árbol cuando el dominio de asignación de una variable en el árbol es vacío
Ejemplos
Problema 8 damas.
Criptoaritmética.

Problemas de satisfacción de restricciones, II
Los problemas discretos (dominio finito) se pueden resolver utilizando búsqueda:
Estado inicial: todas las variables sin asignar
Profundidad máxima=número de variables=profundidad de todas las soluciones
Se puede utilizar, por tanto, búsqueda en profundidad.
Cardinal espacio búsqueda=producto de cardinales de los dominios de las variables
Se puede hacer:
Eliminación de ramas en donde alguna restricción no se satisface (backtracking)
Propagación de restricciones, para reducir los posibles valores de las variables por asignar.

Otros ejemplos
Problema del viajante de comercio
NLP
Problemas de análisis sintáctico
Ejercicios de la hoja 3
Localización de una moneda falsa.
Reconocimiento de cadenas de caracteres para una expresión regular.
Etc.